package algorithm.Sort;

import algorithm.Util.Examination;

import java.util.Arrays;

/**
 * @program:Algorithm
 * @description:快速排序
 * @author:Lance
 * @create:2020-09-14 21:16
 **/
public class QuickSort {
    public static void main(String[] args) {
        int [] arr = {12,6,5,4,3,2,1,2,52,44,155,157,15,177,135,122,852,300,100,125,120,4,50,13,120,
                3,2,1,2,52,44,155,157,15,177,135,12,6,5,4,3,12,6,5,4,3,2,1,2,52,44,155,157,15,177,135,122,852,300,100,125,120,4,50,13,120,
                3,2,1,2,52,44,155,157,15,177,135,12,6,5,4,3,12,6,5,4,3,2,1,2,52,44,155,157,15,177,135,122,852,300,100,125,120,4,50,13,120,
                3,2,1,2,52,44,155,157,15,177,135,12,6,5,4,3,12,6,5,4,3,2,1,2,52,44,155,157,15,177,135,122,852,300,100,125,120,4,50,13,120,
                3,2,1,2,52,44,155,157,15,177,135,12,6,5,4,3};
        QuickSort(arr,0,arr.length-1);
        Examination.start();
        System.out.println(Arrays.toString(arr));
        Examination.end();
    }

    /**
     * 快速排序
     * @param arr 无序数组
     * @return    有序数组
     */
    public static void QuickSort(int [] arr,int left,int right){
        if(left>right){
            return;
        }
        //base存放基数
        int base = arr[left];
        int i = left;int j = right;
        while (i!=j){
            //从右往左找，直到找到比base数值小的
            while(arr[j]>=base&&i<j){
                j--;
            }
            //从左往右找，直到找到比base数值大的数
            while(arr[i]<=base&&i<j){
                i++;
            }
            //前两个while循环结束表示找到相应的位置，开始交换位置
            if(i<j){
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        arr[left]  = arr[i];
        arr[i] = base;
        //递归，继续向基准的左右两边执行和上面一样的操作，i的索引处为上面已经确定的基准位置，无需再处理
        QuickSort(arr, left, i-1);
        QuickSort(arr,i+1,right);
    }
}
